package com.dycong.common.dataStructuresAndAlgorithms.hash;

// SeparateChainingHashTable class
//
// CONSTRUCTION: with an approximate initial size or default of 101
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x
// Hashable find( x )     --> Return item that matches x
// void makeEmpty( )      --> Remove all items
// int hash( String str, int tableSize )
//                        --> Static method to hash strings
// ******************ERRORS********************************
// insert overrides previous value if duplicate; not an error



/**
 * Separate chaining table implementation of hash tables.
 * Note that all "matching" is based on the equals method.
 *
 * @author Mark Allen Weiss
 */
public class SeparateChainingHashTable {
    /**
     * Construct the hash table.
     */
    public SeparateChainingHashTable() {
        this(DEFAULT_TABLE_SIZE);
    }

    /**
     * Construct the hash table.
     *
     * @param size approximate table size.
     */
    public SeparateChainingHashTable(int size) {
        theLists = new LinkedList[nextPrime(size)];
        for (int i = 0; i < theLists.length; i++)
            theLists[i] = new LinkedList();
    }

    /**
     * Insert into the hash table. If the item is
     * already present, then do nothing.
     *
     * @param x the item to insert.
     */
    public void insert(Hashable x) {
        LinkedList whichList = theLists[x.hash(theLists.length)];
        LinkedListItr itr = whichList.find(x);

        if (itr.isPastEnd())
            whichList.insert(x, whichList.zeroth());
    }

    /**
     * Remove from the hash table.
     *
     * @param x the item to remove.
     */
    public void remove(Hashable x) {
        theLists[x.hash(theLists.length)].remove(x);
    }

    /**
     * Find an item in the hash table.
     *
     * @param x the item to search for.
     * @return the matching item, or null if not found.
     */
    public Hashable find(Hashable x) {
        return (Hashable) theLists[x.hash(theLists.length)].find(x).retrieve();
    }

    /**
     * Make the hash table logically empty.
     */
    public void makeEmpty() {
        for (int i = 0; i < theLists.length; i++)
            theLists[i].makeEmpty();
    }

    /**
     * A hash routine for String objects.
     *
     * @param key       the String to hash.
     * @param tableSize the size of the hash table.
     * @return the hash value.
     */
    public static int hash(String key, int tableSize) {
        int hashVal = 0;

        for (int i = 0; i < key.length(); i++)
            hashVal = 37 * hashVal + key.charAt(i);

        hashVal %= tableSize;
        if (hashVal < 0)
            hashVal += tableSize;

        return hashVal;
    }

    private static final int DEFAULT_TABLE_SIZE = 101;

    /**
     * The array of Lists.
     */
    private LinkedList[] theLists;

    /**
     * Internal method to find a prime number at least as large as n.
     *
     * @param n the starting number (must be positive).
     * @return a prime number larger than or equal to n.
     */
    private static int nextPrime(int n) {
        if (n % 2 == 0)
            n++;

        for (; !isPrime(n); n += 2)
            ;

        return n;
    }

    /**
     * @param n the number to test.
     * @return the result of the test.
     * @see 是否是质数:for (i = 3; i <= sqrt(Num); i += 2)
     * Internal method to test if a number is prime.
     * Not an efficient algorithm.
     */
    private static boolean isPrime(int n) {
        if (n == 2 || n == 3)
            return true;

        if (n == 1 || n % 2 == 0)
            return false;

        for (int i = 3; i * i <= n; i += 2)
            if (n % i == 0)
                return false;

        return true;
    }

    public void rehash() {
        LinkedList[] oldList = theLists;
        theLists = new LinkedList[nextPrime(2 * oldList.length)];
        for (int i = 0; i < theLists.length; i++)
            theLists[i] = new LinkedList();

        for (int i = 0; i < oldList.length; i++)
//                for (MyInteger integer:oldList[i])
//                    insert(integer)
            ;

    }


    // Simple main
    public static void main(String[] args) {
        SeparateChainingHashTable H = new SeparateChainingHashTable();

        final int NUMS = 4000;
        final int GAP = 37;

        System.out.println("Checking... (no more output means success)");

        for (int i = GAP; i != 0; i = (i + GAP) % NUMS)
            H.insert(new MyInteger(i));
        for (int i = 1; i < NUMS; i += 2)
            H.remove(new MyInteger(i));

        for (int i = 2; i < NUMS; i += 2)
            if (((MyInteger) (H.find(new MyInteger(i)))).intValue() != i)
                System.out.println("Find fails " + i);

        for (int i = 1; i < NUMS; i += 2) {
            if (H.find(new MyInteger(i)) != null)
                System.out.println("OOPS!!! " + i);
        }
    }

}

/**
 * todo hashTable标准库的实现与此设计不尽相同,标准库的数组+链表，数组存储的不是LinkedList的Object,标准库里为Entry.
 * todo 标准库的数组就是Entry[]数组 final int hash;final K key;V value;Entry<K,V> next;
 */
/*
        public synchronized V get(Object key) {
            Hashtable.Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;
            for (Hashtable.Entry<?,?> e = tab[index]; e != null ; e = e.next) {
                if ((e.hash == hash) && e.key.equals(key)) {
                    return (V)e.value;
                }
            }
            return null;
        }


private static class Entry<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Hashtable.Entry<K,V> next;

    protected Entry(int hash, K key, V value, Hashtable.Entry<K,V> next) {
        this.hash = hash;
        this.key =  key;
        this.value = value;
        this.next = next;
    }

    @SuppressWarnings("unchecked")
    protected Object clone() {
        return new Hashtable.Entry<>(hash, key, value,
                (next==null ? null : (Hashtable.Entry<K,V>) next.clone()));
    }

    // Map.Entry Ops

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }

    public V setValue(V value) {
        if (value == null)
            throw new NullPointerException();

        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }

*/

/*
*todo HashMap的链表Node
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }
 */



/*
*todo HashMap的红黑树（数组的链表大于8时转化为红黑树）
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }


final HashMap.TreeNode<K,V> root() {
    for (HashMap.TreeNode<K,V> r = this, p;;) {
        if ((p = r.parent) == null)
            return r;
        r = p;
    }
}
 */


    /**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    /*
    *todo HashMap的集合真正创建在putVal()方法里，构造方法里只是指定，初始容量及负载因子
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
    */




